﻿/*
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
*/

#include "AllInc.h"

class Solution {
public:
	vector<string> generateParenthesis(int n) 
	{
		vector<string> res;
		generateParenthesisDFS(n, n, "", res);
		return res;
	}

	void generateParenthesisDFS(int left, int right, string out, vector<string> &res) 
	{
		if (left > right)
		{
			return;
		}
		if (left == 0 && right == 0)
		{
			res.push_back(out);
		}
		else 
		{
			if (left > 0) 
				generateParenthesisDFS(left - 1, right, out + '(', res);
			if (right > 0) 
				generateParenthesisDFS(left, right - 1, out + ')', res);
		}
	}
};

//int main()
//{
//	Solution s;
//	auto result = s.generateParenthesis(3);
//
//	return 0;
//}